home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / extmath.exe / EXTDIVA.S < prev    next >
Encoding:
Text File  |  1993-01-06  |  6.9 KB  |  278 lines
  1. ; 64-bit x 64-bit unsigned divide
  2. ; Bit-match algorithm
  3. ;
  4. ; Tim Victor, January 2, 1993
  5. ;
  6. ; Callable from C as follows:
  7. ; int ExtDiv(dividend, divisor, quotient, remainder);
  8. ;   returns 1 for attempted divide-by-zero, 0 otherwise
  9. ;
  10.  
  11.         .model  small
  12.         .data
  13. ; jump table for shifting and storing dividend
  14. jtable  dw   store0
  15.         dw   store1
  16.         dw   store2
  17.         dw   store3
  18.  
  19.         .code
  20.         public _ExtDiv
  21. _ExtDiv proc near
  22.  
  23.         push bp         ; save caller's stack frame
  24.         mov  bp,sp      ; address arguments
  25.         push si         ; save caller's register vars
  26.         push di
  27.  
  28. ;scan divisor, looking for non-zero word
  29.         sub  ax,ax
  30.         sub  cx,cx
  31.         mov  si,[bp+6]          ; get divisor addr
  32.         or   ax,[si+6]
  33.         jnz  nzdivis
  34.  
  35.         inc  ch
  36.         or   ax,[si+4]
  37.         jne  nzdivis
  38.  
  39.         inc  ch
  40.         or   ax,[si+2]
  41.         jne  nzdivis
  42.  
  43.         inc  ch
  44.         or   ax,[si]
  45.         jne  nzdivis
  46.  
  47. ; divide-by-zero detected; return 1
  48. dbz:    mov  ax,1               ; retcode <- 1
  49.         jmp  exithere
  50.  
  51. ; ax contains highest-order non-zero divisor word,
  52. ; ch contains right-shift word count;
  53. ; now find highest-order set bit, keep count in cl
  54. nzdivis:
  55.         inc  cl
  56.         shl  ax,1
  57.         jnc  nzdivis
  58.  
  59. ; scan dividend, looking for non-zero word
  60. ; adjust word and bit counts in cl/ch
  61.         sub  ax,ax
  62.         mov  di,[bp+4]          ; get dividend addr
  63.         or   ax,[di+6]
  64.         jnz  nzdivid
  65.  
  66.         dec  ch
  67.         or   ax,[di+4]
  68.         jne  nzdivid
  69.  
  70.         dec  ch
  71.         or   ax,[di+2]
  72.         jne  nzdivid
  73.  
  74.         dec  ch
  75.         or   ax,[di]
  76.         je   zeroquot
  77.  
  78. ; ax contains highest-order non-zero dividend word,
  79. ; find highest-order set bit
  80. nzdivid:
  81.         dec  cl
  82.         shl  ax,1
  83.         jnc  nzdivid
  84.  
  85. ; if bit-shift count went negative, borrow from word-shift count
  86.         test cl,080h
  87.         jz   nobitbor
  88.         add  cl,16
  89.         dec  ch
  90. nobitbor:
  91.  
  92. ; double word-shift for jump-table offset;
  93. ; if value was negative, bail cuz quotient is zero
  94.         shl  ch,1
  95.         jnc  nzquot
  96.  
  97. ; divisor > dividend, so quotient is zero
  98. zeroquot:
  99.         mov  si,[bp+4]          ; address dividend
  100.         mov  di,[bp+0Ah]        ; address remainder
  101.         mov  ax,[si]            ; remainder <= dividend
  102.         mov  [di],ax
  103.         mov  ax,[si+2]
  104.         mov  [di+2],ax
  105.         mov  ax,[si+4]
  106.         mov  [di+4],ax
  107.         mov  ax,[si+6]
  108.         mov  [di+6],ax
  109.  
  110.         sub  ax,ax              ; retcode <= 0
  111.         mov  di,[bp+8]          ; address quotient
  112.         mov  [di],ax            ; quotient <= 0
  113.         mov  [di+2],ax
  114.         mov  [di+4],ax
  115.         mov  [di+6],ax
  116.         jmp  exithere
  117. nzquot:
  118.  
  119. ; save bit shift for loop count
  120.         push cx
  121.  
  122. ; load 5-word accum from dividend (addr still in di)
  123. ;  - bp reg gets blasted here; makes args harder to find
  124.         sub  si,si
  125.         mov  ax,[di]
  126.         mov  bx,[di+2]
  127.         mov  dx,[di+4]
  128.         mov  bp,[di+6]
  129.  
  130. ; right-shift dividend to match high-bit of MSW w/ divisor
  131.         or   cl,cl
  132.         je   nobitshft
  133. bshftlp:
  134.         shr  bp,1
  135.         rcr  dx,1
  136.         rcr  bx,1
  137.         rcr  ax,1
  138.         rcr  si,1
  139.         dec  cl
  140.         jnz  bshftlp
  141. nobitshft:
  142.  
  143. ; switch based on word-shift count, load accum appropriately
  144.         xchg ch,cl              ; cl was just zeroed above
  145.         mov  di,cx
  146.         pop  cx                 ; saved bit-shift value makes loop count
  147.         sub  ch,ch              ; only interested in low byte
  148.         jmp  [jtable+di]
  149.  
  150. ; init accum and quotient storage with zero-word shift
  151. store0:
  152.         mov  di,sp              ; find quotient storage
  153.         mov  di,[di+0Ch]        ; (kinda tricky w/o base reg)
  154.         mov  [di+6],si          ; store partial word in quotient
  155.         sub  si,si
  156.         mov  [di+4],si          ; zero the other three
  157.         mov  [di+2],si
  158.         mov  [di],si
  159.         add  cx,1               ; adjust loop count
  160.         jmp  cmnstore
  161.  
  162. ; init accum and quotient storage with one-word shift
  163. store1:
  164.         mov  di,sp              ; find quotient storage
  165.         mov  di,[di+0Ch]
  166.         mov  [di+6],ax          ; store two words in quotient
  167.         mov  [di+4],si
  168.         mov  ax,bx              ; juggle words in accum
  169.         mov  bx,dx
  170.         mov  dx,bp
  171.         sub  bp,bp              ; zero high word of accum
  172.         mov  [di+2],bp          ; zero out two other quotient words
  173.         mov  [di],bp
  174.         add  cx,17              ; adjust loop count
  175.         jmp  cmnstore
  176.  
  177. ; init accum and quotient storage with two-word shift
  178. store2:
  179.         mov  di,sp              ; find quotient storage
  180.         mov  di,[di+0Ch]
  181.         mov  [di+6],bx          ; store three words in quotient
  182.         mov  [di+4],ax
  183.         mov  [di+2],si
  184.         mov  ax,dx              ; juggle words in accum
  185.         mov  bx,bp
  186.         sub  bp,bp              ; zero two highest words of accum
  187.         mov  dx,bp
  188.         mov  [di],bp            ; zero out other quotient word
  189.         add  cx,33              ; adjust loop count
  190.         jmp  cmnstore
  191.  
  192. ; init accum and quotient storage with three-word shift
  193. store3:
  194.         mov  di,sp              ; find quotient storage
  195.         mov  di,[di+0Ch]
  196.         mov  [di+6],dx          ; store four words in quotient
  197.         mov  [di+4],bx
  198.         mov  [di+2],ax
  199.         mov  [di],si
  200.         mov  ax,bp              ; one (partial) word stays in accum
  201.         sub  bp,bp              ; zero out other accum words
  202.         mov  dx,bp
  203.         mov  bx,bp
  204.         add  cx,49              ; adjust loop count
  205. cmnstore:
  206.  
  207. ; point si to divisor, then do it
  208. ; (di still points to quotient)
  209.         mov  si,sp
  210.         mov  si,[si+0Ah]
  211.         jmp  entry1
  212.  
  213. divloop:
  214. ; shift high bit out of dividend
  215.         shl  word ptr [di],1
  216.         rcl  word ptr [di+2],1
  217.         rcl  word ptr [di+4],1
  218.         rcl  word ptr [di+6],1
  219.  
  220. ; shift bit into accumulator
  221.         rcl  ax,1               
  222.         rcl  bx,1
  223.         rcl  dx,1
  224.         rcl  bp,1
  225.  
  226. ; compare divisor to accum
  227. entry1:
  228.         cmp  bp,[si+6]
  229.         jb   nosub
  230.         ja   subdiv
  231.  
  232.         cmp  dx,[si+4]
  233.         jb   nosub
  234.         ja   subdiv
  235.  
  236.         cmp  bx,[si+2]
  237.         jb   nosub
  238.         ja   subdiv
  239.  
  240.         cmp  ax,[si]
  241.         jb   nosub
  242.  
  243. subdiv:
  244. ; if accum > divisor, subtract divisor
  245.         sub  ax,[si]
  246.         sbb  bx,[si+2]
  247.         sbb  dx,[si+4]
  248.         sbb  bp,[si+6]
  249.  
  250. ; put a one bit in quotient
  251.         inc  word ptr [di]
  252.  
  253. nosub:
  254.         loop divloop
  255.  
  256. ; done, store remainder
  257.         mov  si,sp
  258.         mov  si,[si+0Eh]        ; address remainder
  259.         mov  [si],ax
  260.         mov  [si+2],bx
  261.         mov  [si+4],dx
  262.         mov  [si+6],bp
  263.  
  264. ; signal success
  265.         sub  ax,ax
  266.  
  267. ; restore caller's regs
  268. exithere:
  269.         pop  di
  270.         pop  si
  271.         pop  bp
  272.  
  273.         ret
  274.  
  275. _ExtDiv endp
  276.         end
  277.  
  278.